The invention relates to a technique for generating a pseudo-randomly ordered sequence of integers. In particular, the invention relates to a method and apparatus for generating sequences for an uncoordinated frequency hopping wireless communication system.
In the last decade, progress in radio and VLSI technology has fostered widespread use of radio communications in consumer applications. Portable devices, such as mobile radios, can now be produced having acceptable cost, size and power consumption.
Although wireless technology is today focused mainly on voice communications (e.g., with respect to hand-held radios), this field will likely expand in the near future to provide greater information flow to and from other types of nomadic devices and fixed devices. More specifically, it is likely that further advances in technology will provide very inexpensive radio equipment which can be easily integrated into many devices. This will reduce the number of cables currently used. For instance, radio communication can eliminate or reduce the number of cables used to connect master devices with their respective peripherals.
The aforementioned radio communications will require an unlicensed band with sufficient capacity to allow for high data rate transmissions. A suitable band is the ISM (Industrial, Scientific and Medical) band at 2.4 GHz, which is globally available. This band provides 83.5 MHz of radio spectrum.
To allow different radio networks to share the same radio medium without coordination, signal spreading is usually applied. In fact, the FCC in the United States currently requires radio equipment operating in the 2.4 GHz band to apply some form of spreading when the transmit power exceeds about 0 dBm. Spreading can either be at the symbol level by applying direct-sequence spread spectrum or at the channel level by applying frequency hopping (FH) spread spectrum. The latter is attractive for the radio applications mentioned above since it more readily allows the use of cost-effective radios.
In frequency hopping systems, optimal interference immunity is obtained by hopping over the entire 83.5 MHz band on average. At the same time, implementation is facilitated by using a narrow channel, for example, 1 MHz.
Most of the time, different FH radios use different hop frequencies, but occasionally the units may collide if they happen to select the same hop frequency. In order to reduce the probability of this occurrence, each link should preferably have its own FH sequence, since the deployment of two links with the same FH sequence would result in constant collisions if the sequences are in phase. Also, the units should use FH sequences that show low cross-correlation. It is therefore desirable to derive as many different FH sequences as possible which show low cross-correlation. In the optimal case, the FH sequences should be orthogonal. However, this requires the synchronization of different radio units which is both impractical and currently not permitted by the FCC in the United States.
In the above-referenced patent application entitled "Frequency Hopping Piconets in an Uncoordinated Wireless Multi-User System" by the present inventor, a system is disclosed for forming a wireless scatter network of multiple uncoordinated "piconets". As shown in FIG. 1, a network 10 comprises three piconets (A, B and C), each of which communicates with a subset of the wireless units 100, 102, 104, 106 and 108. In the scatter network, piconets are dynamically formed and abandoned to suit the communication requirements of wireless units within the network. For instance, piconet C is established to carry out the exchange of information between units 104 and 106.
All piconets make use of the same radio medium. This radio medium is divided into a large number of subchannels, each centered around a certain carrier frequency. All units in the same piconet synchronously hop from one channel to the next channel. Because different piconets use different pseudo-random hopping sequences, interference immunity is obtained by frequency hopping through a sequence of channels selected in, for example, the 2.4 GHz band. Further details regarding the communication of information using the frequency hopping technique can be found in commonly assigned U.S. patent application Ser. No. 08/685,069, entitled "Short-Range Radio Communications System and Method of Use", which was filed on Jul. 23, 1996, and which is incorporated herein in its entirety by reference.
In each piconet, one of the wireless units is designated as a master and the remaining units are slaves. The frequency hopping sequence for each piconet is generated at the master unit on the basis of the master unit's address. The phase within the selected hopping sequence is a function of the master's free-running clock. Once a connection has been established between a master and a slave, the master unit conveys its master address and master clock to the slave unit. The master address and master clock are then used to define the virtual frequency hopping channel that will be used in communications between the master unit and all of the slave units associated with the master unit in the piconet.
To generate the necessary hop frequencies, each unit 100 . . . 108 includes a frequency hop generator 112 . . . 120, respectively. An exemplary frequency hop (FH) generator is shown in FIG. 2. The FH generator 200 shown there receives a clock "CLK" input (representative of the master's clock) and an address input (representative of the master's address), and generates a hop number therefrom. Changing the clock generates a different hop number within the sequence. In other words, changing the clock selects a different phase within the sequence.
In the second above-referenced patent application entitled "Contemporaneous Connectivity to Multiple Piconets" by the present inventor, a technique is described for providing connectivity between different piconets. In this disclosure, a unit can switch from one piconet to another by changing the address and the clock. For example, as shown in FIG. 1, for piconet A, master address.sub.-- A and clock.sub.-- A are used, whereas for piconet B, master address.sub.-- B and clock.sub.-- B are used. Unit 108 participating as a slave in piconet.sub.-- A will apply address.sub.-- A and clock.sub.-- A to follow the FH channel in piconet A. If this unit wants to participate in piconet.sub.-- B as a slave, it simply changes to address.sub.-- B and clock.sub.-- B. Alternatively, unit 108 can be participating in piconet A as a master, yet switches to piconet B to participate as a slave. These switches preferably occur in real-time so that the unit can jump from one piconet to another piconet, such that it virtually participates in all piconets simultaneously.
In systems such as described above, it is desirable to quickly switch from one sequence to another. Conventional systems do not readily satisfy this objective. For instance, if the sequence is of sizeable format, the sequence can be generated off-line using some pseudo-random generator process, and then downloaded into RAM memory. The RAM is subsequently read out using the clock to address the RAM. However, off-line processing and downloading into RAM imposes considerable time and power requirements. In addition, the sequence length is restricted by the limited size (capacity) of the RAM. Also, since the contents of the RAM represent the frequency hopping sequence, fast switching between piconets that use different sequences is not possible because the RAM contents can not be changed quickly.
Another method for generating sequences is through the use of linear or non-linear feedback registers. These registers are used as number generators in encryption routines and general cryptographic procedures. By clocking the registers, a cycle is followed whose sequence and length depends on the feedback connections. Different cycles can be chosen by changing the feedback connections. A problem with these registers is that the number of sequences with suitable properties is limited. Some settings (corresponding to respective addresses) will produce very short sequences with inadequate properties, while other settings will produce very long sequences.
In addition, the application shown in FIG. 1 requires a direct mapping of the clock value CLK onto a hop number. This mandates that the FH generator not have a memory, since this would be unsatisfactory when jumping from one piconet to another piconet. For a feedback register, this means that the register has to be initialized with the clock value after which the feedback register is clocked one or several times after which the hop number is read out. For the next and subsequent clock values, this procedure has to be repeated.
Still other techniques for generating pseudo-random sequences are discussed in "Spread Spectrum Communications Handbook", Simon et al., McGraw-Hill, Inc., copyright 1994, chapter 5. These techniques are also generally unsuited for the real-time requirements imposed by the application discussed above.